package daily_exercise;

public class bag01 {

    public static int maxValue(int[] w, int[] v, int capacity){
        if (w == null || v == null || w.length != v.length || w.length == 0){
            return 0;
        }
        int[][] dp = new int[w.length][capacity + 1];
        // 赋值边界（dp第0行和第0列都是0）
        // 普遍情况：1.当剩余容量不够装i,dp[i][w]=dp[i-1][w];
        // 2.当剩余容量够装i,dp[i][w]=Math.max(装当前物品(dp[i-1][w-w(i-1)]+v[i])，
        // 不装当前物品(dp[i][w]=dp[i-1][w]))
        for (int j = 0; j <= capacity; j++) {
            dp[0][j] = w[0] <= j ? v[0] : 0;
        }
        for (int i = 1; i < w.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j - w[i] < 0){
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
                }
            }
        }
        return dp[w.length - 1][capacity];
    }

    public static void main(String[] args) {
        int[] w = {2,1,3,2};
        int[] v = {12,10,20,15};
        int capacity = 5;
        System.out.println(maxValue(w, v, capacity));
    }
}
